/*
 *  Brno University of Technology
 *
 *  Copyright (C) 2009-2010 by Brno University of Technology and the contributors
 *
 *  Complete list of developers available at our web site:
 *
 *       http://spl.utko.feec.vutbr.cz
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with this program.  If not, see http://www.gnu.org/licenses/.
 */
/**
 * Evolutionary framework is library for genetic programming.
 */
package cz.vutbr.feec.utko.ef.grammar;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map.Entry;

import org.apache.log4j.Logger;

import cz.vutbr.feec.utko.ef.core.Random;
import cz.vutbr.feec.utko.ef.individuals.ActionTree;
import cz.vutbr.feec.utko.ef.individuals.Action;
import cz.vutbr.feec.utko.ef.individuals.Constants;

/**
 * The Class Grammar defines grammar for genetic programming. The grammar
 * describes structures of programs, which describes a structure of programs.
 * For example a grammar depicted in the following figure. The grammar defines
 * that the only follower of the ROOT nonterminal can be E (expression)
 * nonterminal and the possible nonterminals of E can be "E+E", "E-E" and "E".
 * 
 * \image html images/grammar.jpg
 * 
 * \code Grammar g = new Grammar(); g.addRule("ROOT", new Rule("E"));
 * 
 * // add the rules to the grammar g.addRule("E", new Rule(plus, "E", "E"), new
 * Rule(minus, "E", "E"), new Rule(number)); \endcode
 */
public class Grammar {
	
	/**
	 * The Class RuleSetFromToken contain all the rules originating from a
	 * particular token, e.g. A->B|C|D|EA.
	 */
	private HashMap<String, RuleSetFromToken> rules = new HashMap<String, RuleSetFromToken>();
	
	/** The log. */
	private Logger log = Logger.getLogger(Grammar.class);
	
	/** The input parameters list. */
	private LinkedList<ActionTree> inputParametersList = new LinkedList<ActionTree>();

	/**
	 * Adds the rule to the grammar.
	 * 
	 * @param fromToken
	 *            the token from which this rule is originating
	 * @param sucessors
	 *            the actions to be performed
	 */
	public void addRule(String fromToken, Rule... sucessors) {
		if (rules.keySet().contains(fromToken)) {
			throw new RuntimeException("The key '" + fromToken
					+ "' was already defined");
		}
		for (Rule sucessor : sucessors) {
			assert sucessor.getFromToken() == null;
			sucessor.setParentToken(fromToken);
		}
		RuleSetFromToken rs = new RuleSetFromToken(sucessors);
		rules.put(fromToken, rs);
	}

	/**
	 * Compile the context free grammar and compute all the necessary
	 * information about the grammar.
	 */
	public void compile() {
		int changes;
		do {
			changes = 0;
			// for each set of rules originating from symbol E -> X | Y | Z...
			for (Entry<String, RuleSetFromToken> e : rules.entrySet()) {
				log.debug("Computing rule " + e.getKey());
				RuleSetFromToken ruleSet = e.getValue();
				changes += updateShortestProdLengths(ruleSet);
				log.debug(this);
			}
		} while (changes != 0);

		if (rules.get("ROOT") == null) {
			throw new RuntimeException("The 'ROOT' token was not defined.");
		}
		if (rules.get("ROOT").getProductionLength() == Constants.INFINITE) {
			throw new RuntimeException(
					"The 'ROOT' node is not reachable, production length is infinite. "
							+ this);
		}

		// validate that each rule has finite production length
		for (Entry<String, RuleSetFromToken> e : rules.entrySet()) {
			for (Rule r : e.getValue().getSuccessors()) {
				if (r.hasInfiniteProductionLength()) {
					throw new RuntimeException("Rule " + r
							+ " has infinite production length.");
				}
			}
		}
	}

	/**
	 * Gets the number of program input parameters.
	 * 
	 * @return the number of program input parameters
	 */
	public int getNumberOfProgramInputParameters() {
		return inputParametersList.size();
	}

	/**
	 * Gets the production length. The production length stands for the shortest
	 * height of the tree to reach terminals at all nodes.
	 * 
	 * @param token
	 *            the token
	 * 
	 * @return the production length
	 */
	public int getProductionLength(String token) {
		RuleSetFromToken rule = rules.get(token);
		if (rule == null) {
			log.debug("Geting length for token " + token
					+ " but it is not available.");
			throw new RuntimeException("The token " + token
					+ " was not defined in grammar.");
		}
		int res = rule.getProductionLength();

		log.debug("Geting length for token " + token + ", prod. len:" + res);
		return res;
	}

	/**
	 * Gets the program input parameters.
	 * 
	 * @param index
	 *            the index
	 * 
	 * @return the program input parameters
	 */
	public Action getProgramInputParameters(int index) {
		return inputParametersList.get(index);
	}

	/**
	 * Selects a random successor from the set of possible rules.
	 * 
	 * @param token
	 *            the originating nonterminal
	 * @param productionLength
	 *            the max production length
	 * 
	 * @return the random successor
	 */
	public Rule getRandomRule(String token, int productionLength) {
		assert productionLength > 0;
		Rule[] childs = getSuccessor(token);
		HashSet<Rule> rules = new HashSet<Rule>(Arrays.asList(childs));
		Random rnd = new Random();
		while (!rules.isEmpty()) {
			// select random
			int randomIndex = rnd.nextInt(childs.length);
			Rule r = childs[randomIndex];
			// check production length
			int prodLen = r.getProductionLength();
			if (prodLen <= productionLength) {
				return r;
			} else {
				rules.remove(r);
			}
		}
		throw new RuntimeException("Token " + token
				+ " with max. production length " + productionLength
				+ " is not defined.");
	}

	/**
	 * Gets the successor of the token name provided.
	 * 
	 * @param tokenName
	 *            the token name
	 * 
	 * @return the successor
	 */
	public Rule[] getSuccessor(String tokenName) {
		return rules.get(tokenName).getSuccessors();

	}

	/**
	 * Gets description of rule in a human readable format.
	 * 
	 * @param r
	 *            the rule
	 * 
	 * @return the resulting description of rule
	 */
	private String printRule(Rule r) {
		String s = r.getFromToken() + "->";
		for (int i = 0; i < r.getChildTokens().length; i++) {
			s += r.getChildTokens()[i] + ",";
		}
		return s;
	}

	/**
	 * Registers input parameter to the grammar.
	 * 
	 * @param inputParameter
	 *            the new input parameter of genetic program
	 */
	public void registerInputParameter(ActionTree inputParameter) {
		inputParameter.setInputParameter(true);
		inputParametersList.add(inputParameter);
	}

	/* (non-Javadoc)
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		String res = "";
		for (Entry<String, RuleSetFromToken> e : rules.entrySet()) {
			for (Rule r : e.getValue().getSuccessors()) {
				r.getFromToken().equals(e.getKey());
				res += printRule(r) + "[Action: " + r.getAction().getSymbol() + "]" + " (" + e.getValue().getProductionLength()
						+ " / " + r.getProductionLength() + ")\n";
			}
		}
		log.debug(res);
		return res;
	}

	/**
	 * Update shortest production lengths.
	 * 
	 * @param ruleSet
	 *            the rule set
	 * 
	 * @return the int
	 */
	private int updateShortestProdLengths(RuleSetFromToken ruleSet) {
		int changes = 0;
		int min = Integer.MAX_VALUE;
		for (Rule r : ruleSet.getSuccessors()) {
			if (r.isTerminal()) {
				if(getProductionLength(r.getFromToken()) != 1) {
					changes++;
				}
				r.setProductionLength(1);
				ruleSet.setProductionLength(1);
				log.debug("Terminal found -> changes " + changes);
				min = 1;
			} else {
				changes += updateSucessors(r);
				log.debug("Ruleset changes " + changes);
				if (r.getProductionLength() < min) {
					min = r.getProductionLength();
				}
			}
		}
		// nastavit minimum z produc
		assert min > 0;
		ruleSet.setProductionLength(min);
		return changes;
	}

	/**
	 * Update successors.
	 * 
	 * @param r
	 *            the rule
	 * 
	 * @return the int
	 */
	private int updateSucessors(Rule r) {
		int changes = 0;
		int max = 1;
		for (String s : r.getChildTokens()) {
			int tmp = getProductionLength(s);
			log.debug("Comparing: " + tmp);
			assert tmp > 0;
			if (max < tmp) {
				max = tmp;
			}
		}

		if (max != Integer.MAX_VALUE && r.getProductionLength() > max + 1) {
			r.setProductionLength(max + 1);
			log.debug("Seting prod length: " + max);
			assert r.getProductionLength() > 0;
			changes = 1;
			log.debug("RULE CHANGED");
		}
		return changes;
	}

}
